package com.daybyday.day1.day8;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2021/1/15

*/

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class ExamRoom{
    int N;
    TreeSet<Integer> students;

    public ExamRoom(int N){
        this.N = N;
        students = new TreeSet<>();
    }

    public int seat(){
        int student = 0;
        if (students.size() > 0){
            int dist = students.first();
            Integer prev = null;
            for (Integer s : students) {
                if (prev != null){
                    int d = (s - prev) / 2;
                    if( d > dist){
                        dist = d;
                        student = prev + d;
                    }
                }
                prev = s;
            }

            if (N - 1 - students.last() > dist) student = N-1;
        }

        students.add(student);
        return student;
    }

    public void leave(int p){
        students.remove(p);
    }
}

public class Soution {
    Map<Node,Node> visted = new HashMap<>();
    boolean[] visited;
    int count = 0;

    int[] days,costs;

    public static void main(String[] args) {
        Soution s = new Soution();
        /*ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;n2.next = n3;n3.next = n4;
        n4.next = n5;
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        List<Integer> list2 = new ArrayList<>();
        list2.add(1);
        list2.add(2);
        Set<String> set = new HashSet<>();
        set.add(list1.toString());
        set.add(list2.toString());
        System.out.println(set.size());
        TreeNode root = new TreeNode(5);
        TreeNode t4 = new TreeNode(4);
        TreeNode t8 = new TreeNode(8);
        TreeNode t11 = new TreeNode(11);
        TreeNode t13 = new TreeNode(13);
        TreeNode t14 = new TreeNode(4);
        TreeNode t7 = new TreeNode(7);
        TreeNode t2 = new TreeNode(2);
        TreeNode t5 = new TreeNode(5);
        TreeNode t1 = new TreeNode(1);
        root.left = t4;root.right = t8;
        t4.left = t11;t8.left = t13;t8.right = t14;
        t11.left = t7;t11.right = t2;t14.left = t5;t14.right = t1;
        System.out.println(s.pathSum(root, 22));*/
        int[] nums = {1,2,3};
        ArrayList<Integer> list = new ArrayList<>();
        System.out.println(s.permute(nums));
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        boolean isIn[] = new boolean[n];
        dfsSort(nums,isIn,new ArrayList<>(),res,0);
        return res;
    }

    public void dfsSort(int[] nums,boolean[] used,List<Integer> list,List<List<Integer>> res,int depth){
        if (depth == nums.length){
            res.add(list);

            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(!used[i]){
                list.add(nums[i]);
                List<Integer> newList = new ArrayList<>(list);
            //    boolean[] isIn = new boolean[nums.length];
                used[i] = true;
                dfsSort(nums,used,newList,res,depth + 1);
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }

    public int numPairsDivisibleBy60(int[] time) {
        int res = 0;
        int[] couple = new int[60];
        for (int i = 0; i < time.length; i++) {
            couple[time[i] % 60]++;
        }
        res += couple[0] * (couple[0] - 1)/2;
        int i = 1;int j = 59;
        while(i < j){
            res += couple[i++] * couple[j--];
        }
        res += couple[30] * (couple[30] - 1)/2;
        return res;
    }

    public List<List<Integer>> pairSums(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int i = 0, j = nums.length - 1;
        while (i < j){
            if (nums[i] + nums[j] < target){
                i++ ;
                continue;
            }
             if (nums[i] + nums[j] == target) {
                 List<Integer> tmp = new ArrayList<>();
                 tmp.add(nums[i]);tmp.add(nums[j]);
                 res.add(tmp);
                 i++;
                 j--;
             }else{
                 j -- ;
             }
            }
        return res;
    }

    public int minFlips(int a, int b, int c) {
        int count = 0;
        String cs = Integer.toBinaryString(c);
        String as = Integer.toBinaryString(a);
        String bs = Integer.toBinaryString(b);
        int i;
        int a1 = as.length() - 1;
        int b1 = bs.length() - 1;
        for (i = cs.length() - 1; i >= 0; i--) {
                if (cs.charAt(i) == '1'){
                    if(a1 >= 0 && b1 >= 0 && !(as.charAt(a1) == '1' || bs.charAt(b1) == '1')){
                        count++;
                    }else if ((a1 < 0 && b1 >= 0 && bs.charAt(b1) == '0')||(b1 < 0 && a1 >= 0 && as.charAt(a1) == '0') || (a1 < 0 && b1 < 0)){
                        count++;
                    }
                }else{
                    if (a1 >= 0 && as.charAt(a1) == '1') count ++;
                    if ( b1 >= 0 && bs.charAt(b1) == '1') count ++;
                }

            a1--;
            b1--;
        }

        while (a1 >= 0){
            if (as.charAt(a1--) == '1') {
                count ++;
            }
        }
        while (b1 >= 0){
            if (bs.charAt(b1--) == '1') {
                count ++;
            }
        }
        return count;
    }

    public int minOperations(int[] nums) {
        int times = 0;
        int res = nums.length;
        int num1 = 0;
        for (int num : nums) {
            int[] first = getFirst(num);
            num1 += first[1];
            times = Math.max(times,first[0]);
        }
        return res + times + num1;
    }

    public int[] getFirst(int num){
        int[] count = new int[2];
        while (num != 1){
            if ((num & 1) == 0){
                num = num / 2;
                count[0]++;
            }else{
                num = num - 1;
                count[1]++;
            }

        }
       return count;
    }

    public void modify(int[] arr, int op,int idx){
        if(op == 0){
            arr[idx] = arr[idx] + 1;
        }

        if (op == 1){
            for (int i = 0; i < arr.length; i++) {
                arr[i] = arr[i] * 2;
            }
        }
    }

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        int size = nums.length / 3;
        int count = 0;
        int i = 0;
        for (int k = 0; k < nums.length; k++) {
            if (nums[i] == nums[k]){
                count ++ ;
            }else{
                if (count > size){
                    list.add(nums[i]);
                }
                i = k;
                count = 1;
            }
        }
        if (count > size) list.add(nums[i]);
        return list;
    }

    public int numSteps(String s) {
        int count = 0 ;
        StringBuilder sb = new StringBuilder(s);
        int i = sb.length() - 1;
        while (sb.length() != 1){
            count++;
            if ((sb.charAt(i) & 1) == 0){
                sb.deleteCharAt(i);
                i--;
            }else{
                if ((sb.charAt(i - 1) & 1) == 0){

                }
                sb.insert(i,0);

            }
        }
        return count;
    }

    public int maxAbsValExpr(int[] arr1, int[] arr2) {
        int res = Integer.MIN_VALUE;
        for (int j = 0; j < (1 << 3); ++j) {
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for (int i = 0; i < arr1.length; i++) {
                int cur =  ((j & 1) != 0 ? -arr1[i] : arr1[i])
                        + ((j & 2) != 0 ? -arr2[i] : arr2[i])
                        + ((j & 4) != 0 ? -i : i);
                max = Math.max(max, cur);
                min = Math.min(min, cur);
            }
            res = Math.max(res, max - min);
        }
        return res;
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> res = new ArrayList<>();
        Arrays.sort(products);
        int i;int start = 0,end = 0;
        int p = 0;
        int n = searchWord.length();
        int[] pos = new int[n];

        for (i = 0; i < products.length; i++) {
            if (products[i].charAt(0) == searchWord.charAt(0)){
                start = i;
                end ++;
            }
        }
        end = end - 1;
        start = end - start;

        for (int j = start; j <= end ; j++) {
            if (products[j].charAt(p) == searchWord.charAt(p)){
                pos[p++] = j;
            }
        }
        for (int j = 0; j < pos.length; j++) {
            Set<String> set = new HashSet<>();
            set.add(products[pos[j]]);
            if (j + 1 < products.length) set.add(products[j+ 1]);
            if (j + 2 < products.length) set.add(products[j + 2]);

            res.add(new ArrayList<>(set));
        }
        return res;
    }

    public int pathSum(TreeNode root, int sum) {
        if (root == null) return count;
        TreeNode node = root;

        pathSum(node.left,sum);
        pathSum(node.right,sum);
        return count;
    }

    public void dfsSum(TreeNode root,int sum,int tmp){
        if (root == null) return;
        tmp += root.val;
        if (tmp == sum) count++;
        dfsSum(root.left,sum,tmp);
        dfsSum(root.right,sum,tmp);
    }

    public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;

        for (int num : nums) {
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }

        return seenOnce;
    }

    public int mincostTickets(int[] days, int[] costs) {
        for (int i = 0; i < days.length; i++) {
            if (days[i + 1] - days[i] > 3){

            }
        }
        return 0;
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        visited = new boolean[nums.length];
        Arrays.sort(nums);
        dfsCycler(nums,0,ans,cur);
        return ans;
    }

    public void dfsCycler(int[] nums,int id,List<List<Integer>> ans, List<Integer> cur){
        if (id == nums.length){
            ans.add(new ArrayList<>(cur));
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])){
                continue;
            }
            cur.add(nums[i]);
            visited[i] = true;
            dfsCycler(nums,id + 1,ans,cur);
            visited[i] = false;
            cur.remove(id);
        }
    }

    public int longestArithSeqLength(int[] A) {
        int n = A.length;
        int max = 0;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }

        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = 2*A[i] - A[j];
                if (map.containsKey(tmp)) dp[i][j] = dp[map.get(tmp)][i] + 1;
                max = Math.max(max,dp[i][j]);
            }
            map.put(A[i],i);
        }

        return max;
    }

    public void reorderList(ListNode head) {
        Deque<ListNode> queue = new LinkedList<>();
        ListNode move = head.next;
        while (move!= null){
            queue.addLast(move);
            move = move.next;
        }

        ListNode tmp = head;
        tmp.next = null;
        boolean flag = false;
        while (!queue.isEmpty()){
            if (flag){
                tmp.next = queue.removeFirst();
                tmp = tmp.next;
                flag = false;
            }else{
                tmp.next = queue.removeLast();
                flag = true;
                tmp = tmp.next;
            }
        }
        tmp.next = null;
    }

    public void recycler(ListNode cur, ListNode head, ListNode next,ListNode tmp){
        if (cur.next == null){
            tmp.next = cur;
            cur.next = next;
            tmp = next;
            next = next.next;
        }

    }

    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        Set<Integer> row = new HashSet<>();
        Set<Integer> col = new HashSet<>();

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0){
                    row.add(i);
                    col.add(j);
                }
            }
        }

        for (Integer integer : row) {
            for (int i = 0; i < m; i++) {
                matrix[integer][i] = 0;
            }
        }
        for (Integer integer : col) {
            for (int i = 0; i < n; i++) {
                matrix[i][integer] = 0;
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            List<Integer> tmp = new ArrayList<>();
            for (int j = 0; j < matrix[0].length; j++) {
                tmp.add(matrix[i][j]);
            }
            res.add(tmp);
        }

        System.out.println(res);
    }

    public Node cloneGraph(Node node) {
        if (node == null) return node;

        if (visted.containsKey(node)){
            return visted.get(node);
        }

        Node clone = new Node(node.val,new ArrayList<>());
        visted.put(node,clone);
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }
}
